package matrice2D;
import java.util.Vector;



public class Matrice2D {

	int nombreDeLignes = 0 ;
	int nombreDeColonnes = 0 ;
	float[][] matrice ;
	// pour la premiere solution satisfiable
	float[] resultatPourChaqueColonne ;
	int pivotLigne = -1 ;
	int pivotColonne = -1 ;
	
	Vector<float[][]> historique = new Vector<float[][]> () ;
	
	/**
	 * Constructeur,
	 * bien remplir les champs.
	 * traite tout en float.
	 * @param vecteur Vecteur d'equation a partir duquel on construit la matrice initiale.
	 * @param aOptimiser Fonction objectif.
	 */
	public Matrice2D (Vector<Equation2D> vecteur,FonctionAOptimiser2D aOptimiser) {
		this.nombreDeLignes = vecteur.size()+1 ;
		this.nombreDeColonnes = 2+vecteur.size()+2 ;

		matrice = new float[nombreDeLignes][nombreDeColonnes] ;
		
		for (int ligne = 0; ligne < nombreDeLignes ; ligne++) {
			// tout sauf la derniere ligne:
			if (ligne!=(nombreDeLignes-1)) {
				for (int colonne = 0; colonne < nombreDeColonnes ; colonne++) {
					// les 2 premieres colonnes
					if (colonne<2) {
						if (colonne==0)
							matrice[ligne][colonne] = vecteur.get(ligne).XNum ;
						if (colonne==1)
							matrice[ligne][colonne] = vecteur.get(ligne).YNum ;
					}else {
						// on a depasse les deux premieres lignes,
						// il reste a mettre des @
						// en diagonale
						// et le resultat au bout
						if (colonne==2+ligne) {
							if (vecteur.get(ligne).signeEquation==Equation2D.INF_OU_EGAL)
								matrice[ligne][colonne] = 1 ;
							else
								matrice[ligne][colonne] = -1 ;
						}else {
							if (colonne==nombreDeColonnes-1) {
								matrice[ligne][colonne] = vecteur.get(ligne).partieDroiteEquation ;
							}else {
								matrice[ligne][colonne] = 0 ;
							}
						}
					}
				}
			}
			// la derniere ligne
			else {
				for (int colonne = 0; colonne < nombreDeColonnes ; colonne++) {
					// les 2 premieres colonnes
					if (colonne<2) {
						if (colonne==0)
							matrice[ligne][colonne] = -aOptimiser.XNum ;
						if (colonne==1)
							matrice[ligne][colonne] = -aOptimiser.YNum ;
					}else {
					// pas les deux premieres colonnes
						// on met un @ a l avant derniere colonne
						// et 0 a la derniere
						if (colonne==nombreDeColonnes-1) {
							matrice[ligne][colonne] = 0 ;			
						}else {
							if (colonne==nombreDeColonnes-2) {
								if (aOptimiser.optimiser==FonctionAOptimiser2D.MAXIMISER)
									matrice[ligne][colonne] = 1 ;
								else
									matrice[ligne][colonne] = -1 ;
							}else {
								matrice[ligne][colonne] = 0 ;
							}
						}
					}
				}										
			}
		}
		
//		System.out.println("sauvegarde initiale");
		lancerSauvegardeMatrice() ;
		
	}
	
	/**
	 * Sauvegarde l'ancienne matrice (matrice intermediaire) dans le vecteur historique avant le recalcul
	 * de cette derniere (iteration suivante de l'algorithme du simplexe)
	 */
	private void lancerSauvegardeMatrice() {
		float[][] tmp = new float[nombreDeLignes][nombreDeColonnes];

		for (int i = 0; i < nombreDeLignes; i++) {
			for (int j = 0; j < nombreDeColonnes; j++) {
				tmp[i][j]=matrice[i][j] ;
			}
		}
		historique.add(tmp) ;
	}

	public String toString () {
		return afficheMatrice();
	}
	
	/**
	 * Retourne une representation de la matrice actuelle sous forme de chaine de caracteres
	 * @return Une chaine de caractere representant les lignes et les colonnes de la matrice
	 */
	public String afficheMatrice () {
		String res = "" ;
		for (int ligne = 0; ligne < nombreDeLignes ; ligne++) {
			for (int colonne = 0; colonne < nombreDeColonnes ; colonne++) {
				res += matrice[ligne][colonne]+"   " ;
			}
			res += "\n" ;
		}
		return res ;
	}
	
	/**
	 * Retourne la solution initiale sous forme de chaine de caractere
	 * Necessite d'avoir deja calcule la solution initiale avec la methode trouverLaSolutionBasique()
	 * @return La solution initiale sous forme de chaine de caractere
	 */
	public String afficheSolutionInitiale () {
		String res = "" ;
		for (int colonne = 0; colonne < nombreDeColonnes-1 ; colonne++) {
			res+=resultatPourChaqueColonne[colonne]+"   " ;
		}
		return res ;
	}

	/**
	 * Calcule la solution de base realisable.
	 * Necessite d'avoir prealablement cree la matrice.
	 * La methode afficheSolutionInitiale() permet d'afficher cette meme solution.
	 * @see afficheSolutionInitiale()
	 */
	public void trouverLaSolutionBasique() {
		// on ne fais pas de boucle sur Ans
		resultatPourChaqueColonne = new float[nombreDeColonnes-1] ;
		boolean[] lignesEpuisees ;
		lignesEpuisees = new boolean[nombreDeLignes] ;
		for (int i = 0; i < nombreDeLignes; i++) {
			// aucune ligne epuisee
			lignesEpuisees[i] = false ;
		}

		for (int colonne = 0; colonne < nombreDeColonnes-1 ; colonne++) {
			int nombreDEntreeDifferenteDeZero = 0 ;
			int ligneDeLEntreeDifferenteDeZero = 0 ;
			for (int ligne = 0; ligne < nombreDeLignes ; ligne++) {
				
				// si la colonne est differente de 0 !
				if (matrice[ligne][colonne]!=0) {
					nombreDEntreeDifferenteDeZero ++ ;
					ligneDeLEntreeDifferenteDeZero = ligne ;
				}
			}
			if (nombreDEntreeDifferenteDeZero==1 && !lignesEpuisees[ligneDeLEntreeDifferenteDeZero])
			{
//				System.out.println("colonne "+colonne+": on divise "+matrice[ligneDeLEntreeDifferenteDeZero][nombreDeColonnes-1]+" par "+matrice[ligneDeLEntreeDifferenteDeZero][colonne]);
				resultatPourChaqueColonne[colonne] = matrice[ligneDeLEntreeDifferenteDeZero][nombreDeColonnes-1]/matrice[ligneDeLEntreeDifferenteDeZero][colonne] ;
				lignesEpuisees[ligneDeLEntreeDifferenteDeZero] = true ;
			}else {
//				System.out.println("colonne "+colonne+": vaut 0 " ) ;
				resultatPourChaqueColonne[colonne]= 0f ;
			}
		}
	}

	/**
	 * Selectionne le pivot
	 */
	public boolean choisirPivot() {
		// d'abord le choix de la colonne:
		// il faut exclure Ans,
		// prendre le nombre negatif le plus petit,
		// si on n a que des positifs ou nuls,
		// la solution est dejas optimale...
		
		int colonneLaPlusNegative = -1 ;
		for (int colonne = 0; colonne < nombreDeColonnes-1; colonne++) {
//			System.out.println("examen de la colonne "+colonne);
			if (matrice[nombreDeLignes-1][colonne]<0) {
//				System.out.println("la colonne "+colonne+" est negative");
				if (colonneLaPlusNegative == -1) {
					colonneLaPlusNegative = colonne ;
				}else {
					if (matrice[nombreDeLignes-1][colonneLaPlusNegative]>=matrice[nombreDeLignes-1][colonne])
						colonneLaPlusNegative = colonne ;
				}
			}
		}
		
		if (colonneLaPlusNegative==-1) {
			// on a dejas la solution la plus optimale
			System.err.println("solution optimale trouvee");
			return false ;
		}

		//sinon on a la colonne du pivot
		// reste la ligne
		
		// la valeur de la ligne doit etre positive:
		// on prend celle ou le ratio (Ans/pivot est la plus petite)
		
		// pour chaque ligne de la colonne du pivot
		int ligneOptimale = -1 ;
		for (int ligne = 0; ligne < nombreDeLignes-1; ligne++) {
			// si le nombre est positif
			// si il est negatif ou nul on ne peut pas le prendre!
			if (matrice[ligne][colonneLaPlusNegative]>0) {
				if (ligneOptimale==-1)
				{
					ligneOptimale=ligne ;
				}else {
					// on fait le ratio,
					// si le resultat est plus petit,
					// on change l optimal
					if (
(matrice[ligne][nombreDeColonnes-1]/matrice[ligne][colonneLaPlusNegative])<(matrice[ligneOptimale][nombreDeColonnes-1]/matrice[ligneOptimale][colonneLaPlusNegative]))
					{
						ligneOptimale=ligne ;
					}
				}
			}
		}

		// si on a rien trouve :
		if (ligneOptimale==-1) {
			System.err.println("on a pas pu trouver de pivot");
			return false ;
		}

		// sinon le pivot est 
//		(ligneOptimale,colonneLaPlusNegative)
		pivotLigne = ligneOptimale ;
		pivotColonne = colonneLaPlusNegative ;
		
		System.err.println("pivot trouve");
		return true ;
	}

	/**
	 * Effectue le pivot
	 */
	public void effectuerLePivot() {
		if (pivotLigne==-1 || pivotColonne==-1)
		{
			System.err.println("pas de pivot specifie");
			return ;
		}

		float intersection = matrice[pivotLigne][pivotColonne];
		for (int i = 0; i < matrice.length; i++) {		//Pour toutes les lignes differentes de pivotLigne
			if (i != pivotLigne) {
				for (int j = 0; j < matrice[0].length; j++) {		//Pour toutes les colonnes
					matrice[i][j] = (intersection*matrice[i][j]) - (matrice[i][pivotColonne]*matrice[pivotLigne][j]);
				}
			}
		}
		
		//On sauvegarde la nouvelle matrice
		this.lancerSauvegardeMatrice() ;
		
		pivotColonne = -1 ;
		pivotLigne = -1 ;
	}

	/**
	 * Repete les etapes choix du pivot et de realisation du pivot jusqu'a l'obtention de la matrice finale.
	 * L'operation est terminee des qu'il n'y plus de nombre negatif dans la derniere ligne du bas
	 * (à l'exception de la derniere colonne, la colonne reponse).
	 */
	public void trouverTableauFinal() {
		int ind = 1 ;
		while (choisirPivot()) {
			System.out.println("tour numero "+ind);
				effectuerLePivot() ;
		}
		System.out.println("fin ...");
	}
		
	/**
	 * Permet d'obtenir l'historique des versions successives de la matrice au cours des differentes iterations
	 * de la methode du simplexe.
	 * @return Un historique du contenu de la matrice sous forme de chaine de caractere.
	 */
	public String imprimeHistorique() {
		String res = "" ;
		
		for (float[][] mat : historique) {
			for (int i = 0; i < mat.length; i++) {
				for (int j = 0; j < mat[0].length; j++) {
					res+="["+mat[i][j]+"]  " ;
				}
				res+="\n" ;
			}
			res+="\n---\n" ;
		}
		return res ;
	}
}
